package com.klun.project.common.constans.leetcode;
//给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
// 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
// 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
// 示例 1:
// 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
//输出: 6
//解释: 节点 2 和节点 8 的最近公共祖先是 6。
// 示例 2:
// 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
//输出: 2
//解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
// 说明:
// 所有节点的值都是唯一的。
// p、q 为不同节点且均存在于给定的二叉搜索树中。
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树
// 👍 956 👎 0

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayList;
import java.util.List;

public class Solution235 {

	public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
		TreeNode ans = root;
		while (true) {
			if (root.val > p.val && root.val > q.val) {
				ans = ans.left;
			} else if (root.val < p.val && root.val < q.val) {
				ans = ans.right;
			} else {
				break;
			}
		}
		return ans;
	}


	List<TreeNode> pathp = new ArrayList<TreeNode>();
	List<TreeNode> pathq = new ArrayList<TreeNode>();

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		query(root, p);
		query(root, q);
		TreeNode ans = new TreeNode();
		for (int i = 0; i < pathq.size() && i < pathp.size(); i++) {
			if (pathp.get(i) == pathq.get(i)) {
				ans = pathp.get(i);
			} else {
				break;
			}
		}
		return ans;
	}

	public void query(TreeNode root, TreeNode target) {
		pathp.add(root);
		if (root.val > target.val) {
			query(root.left, target);
		} else if (root.val < target.val) {
			query(root.right, target);
		}
	}

	public static void main(String[] args) {
		Solution235 solution = new Solution235();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		TreeNode treeNode = ParseUtils.ArrayToBTree("[3,1,4,null,2]");
		TreeNode treeNode1 = solution.lowestCommonAncestor(treeNode, new TreeNode(), new TreeNode());
		System.out.println(treeNode1);
		System.out.println(treeNode1);
	}
}
